# -*- coding:utf-8 -*-

# 操作复杂度 O(n*n)  平均复杂度O(n)


def cooktail_sort(unsorted):
    for i in range(len(unsorted), 0, -1):
        swapped = False
        for j in range(i, 0, -1):
            if unsorted[j] < unsorted[j - 1]:
                unsorted[j], unsorted[j - 1] = unsorted[j - 1], unsorted[j]
                swapped = True
        for j in range(i):
            if unsorted[j] > unsorted[j + 1]:
                unsorted[j], unsorted[j + 1] = unsorted[j + 1], unsorted[j]
                swapped = True
        if not swapped:
            return unsorted
